package pers.vic.basics.leetcode;

import sun.misc.PostVMInitHook;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

/**
 * @author Vic.xu
 * @description: 30. 串联所有单词的子串 {@literal https://leetcode-cn.com/problems/substring-with-concatenation-of-all-words/}
 * @date: 2020/11/20 0020 16:51
 */
public class J0030_H_FindSubstring {
    /*
    给定一个字符串 s 和一些长度相同的单词 words。找出 s 中恰好可以由 words 中所有单词串联形成的子串的起始位置。
   注意子串要与 words 中的单词完全匹配，中间不能有其他字符，但不需要考虑 words 中单词串联的顺序。
     */

    /**
     * 我真的是个渣渣  只会暴力解决
     */
    public static List<Integer> findSubstring(String s, String[] words) {
        //判断略...

        //words z转map
        Map<String, Integer> wordsMap = new HashMap<>();
        int step = words[0].length();
        //words 总字符长度
        int wordsCharLength = step * words.length;
        for (String word : words) {
            wordsMap.put(word, wordsMap.getOrDefault(word, 0) + 1);
        }

        List<Integer> result = new ArrayList<>();
        //先把s截为words总字符长度的子串， 再把子串截程和words中成员相同程度的子串，且存入map 后和wordsMap 匹配
        for (int i = 0; i <= s.length() - wordsCharLength; i++) {
            String sub = s.substring(i, i + wordsCharLength);
            Map<String, Integer> subMap = new HashMap<>();
            for (int j = 0; j < sub.length(); j += step) {
                String item = sub.substring(j, j + step);
                subMap.put(item, subMap.getOrDefault(item, 0) + 1);
            }
            if (subMap.equals(wordsMap)) {
                result.add(i);
            }
        }
        return result;
    }

    public static boolean equalsMap(Map<String, Integer> map1, Map<String, Integer> map2) {
        if (map1.size() != map2.size()) {
            return false;
        }
        for (Map.Entry<String, Integer> entry : map1.entrySet()) {
            if (!entry.getValue().equals(map2.get(entry.getKey()))) {
                return false;
            }
        }
        return true;
    }

    public static void main(String[] args) {
        /*
                s = "barfoothefoobarman",
          words = ["foo","bar"]
        输出：[0,9]
         */
    /*
    "wordgoodgoodgoodbestword"
["word","good","best","good"]
     */
        String s = "wordgoodgoodgoodbestword";
        String[] words = {"word","good","best","good"};
        //[0,9]
        System.out.println(findSubstring(s, words));

    }
}
